package first.codeTop.tencent;

/**
 * @ClassName LC912
 * @description:
 * @author: 荣燊
 * @create: 2021-10-27 20:33
 **/
public class LC912 {
    // 排序数组
    public static void main(String[] args) {
        int[] a = {5, 1, 1, 2, 0, 0};
        LC912 lc912 = new LC912();
//        lc912.quickSort(a, 0, a.length-1);
        lc912.adjustHeap2(a, 0, a.length);
        for (int i : a) {
            System.out.print(i+", ");
        }
    }

//    public int[] sortArray(int[] nums) {
//
//    }

    // 快排 n*log n
    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left;
        int j = right;
        int temp = nums[i];
        while (i < j) {
            while (i < j && nums[j] > temp) {
                j--;
            }
            swap(nums, i, j);
            while (i< j && nums[i] <= temp) {
                i++;
            }
            swap(nums, i, j);
        }
        quickSort(nums, left, i-1);
        quickSort(nums, i+1, right); // 这里为什么不能是j
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 堆排
//    public int[] maxHeapSort(int[] nums) {
//        // 调整大顶堆
//    }

    // 从i开始遍历，到length结束。nums[i]必是非叶节点
    public void adjustHeap(int[] nums, int i, int length) {
        // 非叶节点
        int temp = nums[i];
        // 比较该非叶节点的 左右孩子节点
        for (int j=2*i+1; j<length; j=2*j+1) {
            // 如果 左节点 小于 右节点
            if (j+1 < length && nums[j] > nums[j+1]) {
                j++;
            }
            // 左节点最大,和父节点比较
            if (nums[j] < temp) {
                nums[i] = nums[j]; //交换父子节点
                // 继续比较下一个（以左节点为根的）
                i = j;
            } else {
                break;
            }
        }
        // 交换,最后一次比较的孩子节点
        nums[i] = temp;
    }

    // 小顶堆
    public void adjustHeap2(int[] nums, int i, int length) {
        // 非叶节点
        int temp = nums[i];

        // 比较该非叶节点的 左右孩子节点
        for (int j=2*i+1; j<length; j=2*j+1) {
            // 如果 左节点 小于 右节点
            if (j+1 < length && nums[j] < nums[j+1]) {
                j++;
            }
            // 左节点最小,和父节点比较
            if (nums[j] < temp) {
                nums[i] = nums[j]; //交换父子节点
                // 继续比较下一个（以左节点为根的）
                i = j;
            } else {
                break;
            }
        }
        // 交换,最后一次比较的孩子节点
        nums[i] = temp;
    }

    public void heap(int[] nums) {
        // 先遍历一次，构造一个大顶堆出来
        for (int i=nums.length/2+1; i>=0; i--) {
            adjustHeap(nums, i, nums.length);
        }
        // 调整堆结构，变成小顶堆
        for (int j=nums.length-1; j>=0; j--) {
            swap(nums, 0, j); // 交换堆顶和最后一个元素
            adjustHeap(nums, 0 ,j); // 重新对堆进行排序
        }
    }


    // 归并排序
//    public int[] mergeSort(int[] nums) {
//
//    }

}
